package com.ting.test.algorithms.排序算法.快速排序;

import java.util.Random;

/**注意: 工程上的快排，都是指随机快排
 *
 * 在arr[L..R]范围上，进行快速排序的过程：
 * 1）用arr[R]对该范围做partition，< arr[R]的数在左部分，== arr[R]的数中间，>arr[R]的数在右部分。假设== arr[R]的数所在范围是[a,b]
 * 2）对arr[L..a-1]进行快速排序(递归)
 * 3）对arr[b+1..R]进行快速排序(递归)
 * 因为每一次partition都会搞定一批数的位置且不会再变动，所以排序能完成
 */
public class 快速排序3版_随机快排 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 41, 9, 2, 5, 3, 8, 2, 3};
         quickSort2(arr);
        for (int num : arr) {
            System.out.print(num + ",");
        }

    }

    private static void quickSort2(int[] arr) {
        if (arr == null || arr.length == 1) {
            return;
        }
        //总的排序范围是0,length-1
         process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        swap(arr,R,L+new Random().nextInt(R-L+1));//在L到R直接随机找一个下标交换位置，防止最差情况发生
        int[] eqArr = helan(arr, L, R);//返回的是在L，R范围内，等于区域的左边界和右边界
        //荷兰问题排序完成后，实际上eqArr[0] 到eqArr[0]范围内的数据已经拍完了，这个范围内都是相等的数
        //接下来就要对该范围左右两边的的数进行排序
        process(arr, L, eqArr[0] - 1);
        process(arr, eqArr[1] + 1, arr[R]);
    }

    /**
     * 目标是对arr在L,R范围内进行荷兰国旗问题的排序
     * 以arr的第R位置的数作为目标数
     *
     * @param arr
     * @param
     * @return
     */
    private static int[] helan(int[] arr, int L, int R) {
        if (L > R) {
            //如果L>R 则 表示非法
            return new int[]{-1, -1};
        }
        if (L == R) {
            return new int[]{L, L};
        }

        int less = L - 1;//左边界默认从下标L-1位置开始
        int more = R;//当前排序的范围是L到R-1 不包含R
        int index = L;
        while (index < more) {
            if (arr[index] < arr[R]) {
                swap(arr, ++less, index++);
            } else if (arr[index] == arr[R]) {
                index++;
            } else {
                swap(arr, --more, index);
            }

        }
        swap(arr, more, R);//最后把R和右边界第一个值进行交换
        return new int[]{less + 1, more};
    }

    private static void swap(int[] arr, int tar1, int tar2) {
        int temp = arr[tar1];
        arr[tar1] = arr[tar2];
        arr[tar2] = temp;
    }
}
